package class08

/*
	给定一个字符串，如果可以在字符串的任意位置添加字符，最少添加几个能让字符串整体都是回文

	算法流程：
		1. 爆裂递归，分析可能性
			递归的参数及返回值，定义为：(s, 0, len(s)-1) 返回凑成回文最少需要填的字符数量
			1.1
				1.1.a终止条件，l==r 的时候，则返回0
				1.1.b终止条件，r-l == 1 的时候，两个数不相等则返回2，否则返回0

			1.2
				可能性分析：假设当前的位置为 i - j
				则存在可能性：
					1. 答案来自 i - j-1   在这个范围上 左边补充一个字符，则对该答案+1
					2. 答案来自 i-1 - j 	 在这个范围上 右边补充一个字符，则对该答案+1
					3. 如果 i == j 字符   答案就等于 i-1 - j-1 这个范围的答案

		2. 优化为dp

		3. 如果有些要的是字符串的可能性的答案，可以通过遍历二维表，反推最后结果
		   如果有多种可能？则可以使用二维表，进行深度遍历，或者广度优先遍历
*/
func getPalindrome(s string) int {
	if len(s) == 0 {
		return 0
	}
	return getPalindromeProcess(s, 0, len(s)-1)

}

func getPalindromeProcess(s string, i, j int) int{
	if i == j {
		return 0
	}
	if j - i == 1 {
		if s[i] == s[j] {
			return 0
		}
		return 2
	}
	var ans int
	p1 := getPalindromeProcess(s, i+1, j) + 1
	p2 := getPalindromeProcess(s, i, j-1) + 1
	ans = min(p1, p2)
	if s[i] == s[j] {
		ans = min(getPalindromeProcess(s, i+1, j-1), ans)
	}
	return ans
}

// dp 表写法
func getPalindromeDp(s string) int {
	N := len(s)
	dp := GetDpByStr(s)
	return dp[0][N-1]
}

func GetDpByStr(s string) [][]int {
	N := len(s)
	dp := make([][]int, N)
	for i:=0; i<N; i++ {
		dp[i] = make([]int, N)
	}

	// 1. 初始化表格
	for i:=0; i<N; i++ {
		if i+1 < N && s[i] != s[i+1] {
			dp[i][i+1] = 2
		}
	}

	/*
				(i, j-1)	 	(i,j)
				(i+1, j-1)		(i+1, j)

			0	 1	2 	3  4
			1	 x  x	x=1, y=3
			2		x	x  x=2,y=4
			3         	x  x
			4			   x
		从下往上，从左往右填表，返回最终结果
	*/
	// 2. 套用递归公式
	for i:=N-3; i>=0; i-- {
		for j:=i+2; j<N; j++ {
			ans := 0
			ans = min(dp[i+1][j] + 1, dp[i][j-1]+1)
			if s[i] == s[j] {
				ans = min(dp[i+1][j-1], ans)
			}
			dp[i][j] = ans
		}
	}
	return dp
}

func getPalindromeStr(s string) string {
	dp:= GetDpByStr(s)

	i := 0
	j := len(s) - 1
	l := 0
	r := j + dp[0][j]
	palindrom := make([]byte, r+1)
	for l <= r {
		if s[i] == s[j] {
			palindrom[l] = s[i]
			palindrom[r] = s[j]
			l++
			r--
			i++
			j--
		} else if dp[i][j-1] < dp[i+1][j] {
			palindrom[l] = s[j]
			palindrom[r] = s[j]
			l++
			r--
			j--
		} else {
			palindrom[l] = s[i]
			palindrom[r] = s[i]
			l++
			r--
			i++
		}
	}
	var ans string
	for i:=0; i<len(palindrom); i++ {
		ans += string(palindrom[i])
	}
	return ans
}